package leetcode.LinkedList;

/**
 * 反转链表2
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 * @author MaoLin Wang
 * @date 2020/2/119:04
 */
public class _92ReverseBetween {
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode temp=head;
        ListNode result=new ListNode(0);
        result.next=head;
        ListNode pre=result;
        for (int i = 1; i <m; i++) {
            pre=pre.next;
            temp=temp.next;
        }
        ListNode reverse = reverse(temp, n - m);
        pre.next=reverse;
        return result.next;
    }
    public static   ListNode reverse(ListNode head,int length){
        ListNode newNode=new ListNode(0);
        ListNode temp=head;
        ListNode next=head.next;
        ListNode tail=null;
        for (int i = 0; i < length+1; i++) {
            if (newNode.next==null){
                newNode.next=temp;
                tail=newNode.next;
                newNode.next.next=null;
            }else {
                temp.next=newNode.next;
                newNode.next=temp;
            }
            if (i!=length){
                temp=next;
                next=next.next;
            }
            //最后一次循环，不需要移动，此时temp在最后一个需要反转的节点，next在下一个节点，如果next非空，则将tail.next=next

        }
        if (next!=null){
            tail.next=next;
        }
        return newNode.next;
    }

    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.next=new ListNode(2);
        l1.next.next=new ListNode(3);
        l1.next.next.next=new ListNode(4);
        l1.next.next.next.next=new ListNode(5);

        ListNode partition = reverseBetween(l1, 2,4);
        ListNode.printNode(partition);
    }
}
